package 二叉树;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
 */

public class _701_二叉搜索树中的插入操作 {
    /**
     * 迭代
     * @param root 根节点
     * @param val 目标值
     * @return TreeNode
     */
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode insertNode = new TreeNode(val);
        if (root == null) {
            return insertNode;
        }
        TreeNode node = root;
        TreeNode parent = root;
        while (node != null) {
            parent = node;
            if (val > node.val) {
                node = node.right;
            } else if (val < node.val) {
                node = node.left;
            } else {
                node.val = val;
                return root;
            }
        }
        if (parent.val > val) {
            parent.left = insertNode;
        } else {
            parent.right = insertNode;
        }
        return root;
    }
}
